package com.fe.class06;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Description 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，
 * 每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
 * 请选择一个合适的排序策略，对这个数组进行排序。
 * @Author sosuke :-)
 * @Date 2022/1/2 23:19
 */
public class Code04_SortArrayDistanceLessK {

    /**
     * 给数组arr排序，arr中每个元素现在的位置和排好序后的位置距离不超过k
     * O(N*logK)，因为构建的堆最大高度是logk
     * @param arr
     * @param k   每个元素现在的位置和排好序后的位置距离
     */
    public static void sortedArrDistanceLessK(int[] arr, int k) {
        if (k == 0) return;
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        //先将0...k-1的数入堆
        while (index <= Math.min(arr.length - 1, k - 1)) {
            heap.add(arr[index++]);
        }

        int i = 0;
        //剩下的数，进一个，出一个最小值
        while (index <= arr.length - 1) {
            heap.add(arr[index++]);
            arr[i++] = heap.poll();
        }
        //数组中已经没有数入堆了，将堆中的数依次出堆
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int testTime = 500000; // 测试次数
        int maxSize = 10; // 数组数据个数
        int maxValue = 100; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int k = (int) (Math.random() * maxSize) + 1;//[1,maxSize]
            int[] arr1 = randomArrayNoMoveMoreK(maxSize, maxValue, k);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            sortedArrDistanceLessK(arr1, k);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice!");

        int k = (int) (Math.random() * maxSize) + 1;//[1,maxSize]
        int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);
        System.out.println("k = " + k);
        System.out.println(Arrays.toString(arr));
        sortedArrDistanceLessK(arr, k);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int k) {
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
        }
        // 先对数组排序
        Arrays.sort(arr);

        // 然后开始随意交换，但是保证每个数距离不超过K
        // 	swap[i] == true, 表示i位置已经参与过交换
        // 	swap[i] == false, 表示i位置没有参与过交换
        boolean[] hasSwap = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int j = Math.min(i + (int) (Math.random() * (k + 1)), arr.length - 1);
            if (!hasSwap[i] && !hasSwap[j]) {
                swap(arr, i, j);
                hasSwap[i] = true;
                hasSwap[j] = true;
            }
        }

        return arr;
    }


}
